3.1 Recursive Fibonacci Sequence

Same procedure as approximating the \(\pi\), compile and then compile

C

#include <R.h>
#include <Rinternals.h>

void fib_c(int *n, int *seq) {
    seq[0] = 0;
    if (*n > 0) {
        seq[1] = 1;
        for (int i = 2; i <= *n; ++i) {
            seq[i] = seq[i - 1] + seq[i - 2];
        }
    }
}

gcc  -I"D:/R GUI/R-4.3.3/R-4.3.3/include" -DNDEBUG     -I"C:/rtools43/x86_64-w64-mingw32.static.posix/include"     -O2 -Wall  -mfpmath=sse -msse2 -mstackrealign  -c c323c43332109.c -o c323c43332109.o
gcc -shared -s -static-libgcc -o c323c43332109.dll tmp.def c323c43332109.o -LC:/rtools43/x86_64-w64-mingw32.static.posix/lib/x64 -LC:/rtools43/x86_64-w64-mingw32.static.posix/lib -LD:/R GUI/R-4.3.3/R-4.3.3/bin/x64 -lR

fib_c <- function(n) {
  seq <- integer(n + 1)
  .C("fib_c", n = as.integer(n), seq = as.integer(seq))$seq
}
fib_c(10)

 [1]  0  1  1  2  3  5  8 13 21 34 55

C++

#include <Rcpp.h>
using namespace Rcpp;

// [[Rcpp::export]]
IntegerVector fib_cpp(int n){
  IntegerVector fibSequence(n + 1);
  fibSequence[0] = 0;
  if (n > 1) {
    fibSequence[1] = 1;
    for (int i = 2; i <= n; ++i) {
      fibSequence[i] = fibSequence[i - 1] + fibSequence[i - 2];
    }
  }
  return fibSequence;
  
}


/***R
fib_cpp(10)
*/

Julia

function fib_jl(n::Int)
  fib = Int[]
  push!(fib, 0)  
  push!(fib, 1)  
  
  
  for i in 3:n
      push!(fib, fib[i - 1] + fib[i - 2])  
  end
  
  return fib
end

fib_jl (generic function with 1 method)

fib_jl <- JuliaCall::julia_eval("fib_jl")
fib_jl(10L)

 [1]  0  1  1  2  3  5  8 13 21 34

Rust

use extendr_api::prelude::*;

#[extendr]
fn fib_rs(n: i32) -> Vec<i32> {
    let mut fib_sequence = vec![0; (n + 1) as usize];
    
    if n > 0 {
        fib_sequence[1] = 1;
        for i in 2..=n as usize {
            fib_sequence[i] = fib_sequence[i - 1] + fib_sequence[i - 2];
        }
    }
    
    fib_sequence
}

fib_rs(10)

 [1]  0  1  1  2  3  5  8 13 21 34 55

FORTRAN

subroutine fib_f(n, fib)
    integer, intent(in) :: n
    integer, intent(out) :: fib(n)
    integer :: i
    
    fib(1) = 0
    fib(2) = 1

    do i = 3, n + 1
        fib(i) = fib(i-1) + fib(i-2)
    end do

end subroutine fib_f

gfortran      -O2  -mfpmath=sse -msse2 -mstackrealign  -c  f95323c5f28535e.f95 -o f95323c5f28535e.o
gcc -shared -s -static-libgcc -o f95323c5f28535e.dll tmp.def f95323c5f28535e.o -LC:/rtools43/x86_64-w64-mingw32.static.posix/lib/x64 -LC:/rtools43/x86_64-w64-mingw32.static.posix/lib -lgfortran -lm -lquadmath -LD:/R GUI/R-4.3.3/R-4.3.3/bin/x64 -lR

fib_fortran <- function(n) {
  n <- n + 1
  .Fortran("fib_f", as.integer(n), fib = integer(n))$fib
}
fib_fortran(10)

 [1]  0  1  1  2  3  5  8 13 21 34 55

R

fib_r <- function(n) {
  fib <- integer(n + 1)
  fib[1] <- 0
  fib[2] <- 1
  for (i in 3:(n+1)) {
    fib[i] <- fib[i - 1] + fib[i - 2]
  }
  return(fib)
}

fib_r(10)

 [1]  0  1  1  2  3  5  8 13 21 34 55

Python

def fib_p(n):
    n = int(n)
    fib_seq = [0, 1]
    for i in range(2, n + 1):
        fib_seq.append(fib_seq[-1] + fib_seq[-2])
    return fib_seq

fib_py <- reticulate::py$fib_p
fib_py(10)

 [1]  0  1  1  2  3  5  8 13 21 34 55

Benchmarks

bench::mark(
  C = fib_c(40),
  Cpp = fib_cpp(40),
  Julia = fib_jl(41L),
  Rust = fib_rs(40),
  FORTRAN = fib_fortran(40),
  R = fib_r(40),
  Python = fib_py(40),
  check = F
)

# A tibble: 7 × 6
  expression      min   median `itr/sec` mem_alloc `gc/sec`
  <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
1 C             2.6µs    2.9µs   280567.   19.23KB     0   
2 Cpp           1.5µs    1.8µs   292772.    7.88KB    29.3 
3 Julia         9.9µs   10.5µs    73230.    5.94KB     0   
4 Rust            7µs    7.3µs   115612.    5.02KB     0   
5 FORTRAN       2.8µs    3.2µs   252404.   17.73KB     0   
6 R             7.4µs    8.4µs   100224.      592B    10.0 
7 Python       52.3µs   55.1µs    15480.     5.2KB     4.15